/*
 *  Number of Inversions
 *
 *  Description:
 *  Count number of inversions in an array
 */

package algs4.sort;

import java.util.Random;
import algs4.basic.Stopwatch;

public class Inversions
{
    public static long count(Comparable[] a) {
        int n = a.length;
        Comparable[] aux1 = new Comparable[n];
        Comparable[] aux2 = new Comparable[n];
        System.arraycopy(a, 0, aux1, 0, n);
        System.arraycopy(a, 0, aux2, 0, n);

        return count(aux1, aux2, 0, n - 1);
    }

    private static long count(Comparable[] src, Comparable[] dst, int lo, int hi) {
        if (hi <= lo) return 0;

        long cnt = 0;
        int mid = (lo + hi) / 2;
        cnt += count(dst, src, lo, mid);
        cnt += count(dst, src, mid + 1, hi);
        cnt += merge(src, dst, lo, mid, hi);

        return cnt;
    }

    private static long merge(Comparable[] dst, Comparable[] src, int lo, int mid, int hi) {
        long cnt = 0;
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) {
            if      (i > mid)                        dst[k] = src[j++];
            else if (j > hi)                         dst[k] = src[i++];
            else if (src[j].compareTo(src[i]) < 0) { dst[k] = src[j++]; cnt += mid - i + 1; }
            else                                     dst[k] = src[i++];
        }

        return cnt;
    }

    private static long bruteCount(Comparable[] a) {
        long cnt = 0;
        for (int i = 1; i < a.length; i++)
            for (int j = i; j > 0; j--)
                if (a[i].compareTo(a[j-1]) < 0)
                    cnt++;

        return cnt;
    }

    private static void show(Comparable[] a) {
        for (Comparable i : a)
            System.out.print(i + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        if (args.length != 1) {
            System.out.println("Usage: Command N");
            System.exit(1);
        }
        int n = Integer.parseInt(args[0]);;

        // Build random array of integer
        Integer[] a   = new Integer[n];
        Random random = new Random(System.currentTimeMillis());
        for (int i = 0; i < n; i++)
            a[i] = random.nextInt(n);

        Stopwatch timer1 = new Stopwatch();
        System.out.print("brute: " + bruteCount(a));
        System.out.printf("(cost %.2f seconds)\n", timer1.elapsedTime());
        Stopwatch timer2 = new Stopwatch();
        System.out.print("merge: " + count(a));
        System.out.printf("(cost %.2f seconds)\n", timer2.elapsedTime());
    }
}
